package net.pragyah.scalgorithms.graphs.shortestpath.allpair

import net.pragyah.scalgorithms.trees.{Tree,Node}

import scala.collection.mutable.HashMap


trait ShortestPathAlgo[A]{
  
    def getShortestPaths(graph:Graph[A]): List[Tree[Vertex[A]]]
    
    implicit def optionToDouble(weight:Option[double]) = weight match{
	    case Some(x) => x
	    case _ => Double.MaxValue
    } 

    
    
    implicit def doubleToOption(weight:double) = Some(weight)
    implicit def intToOption(index:int) = Some(index)

    
    /* get the weight matrix  for direct paths (edges) 
     */
    def weightMatrix(graph:Graph[A]) : Array[Array[Option[double]]] = {
        val retArr= new Array[Array[Option[double]]](graph.vertices.size,graph.vertices.size)
        
        for( i <- 0 to graph.vertices.length-1)
          retArr(i)(i) = Some(0.0)
        graph.edges.foreach( e => retArr(graph.vertices.indexOf(e.v1))(graph.vertices.indexOf(e.v2)) = e.weight)
        retArr
    }
    
    /*get predecessor matrix for direct paths (edges)
     */
   def predecessorMatrix(graph:Graph[A]) : Array[Array[Option[int]]] = {
         val retArr= new Array[Array[Option[int]]](graph.vertices.size,graph.vertices.size)
         graph.edges.foreach( e => retArr(graph.vertices.indexOf(e.v1))(graph.vertices.indexOf(e.v2)) = graph.vertices.indexOf(e.v1))         
         retArr
   }

   
   /*
    * generate the forest of trees for the given graph and a Precedence
    * matrix generated by an all-pair shortest-path algorithm
    */
   def generateForest(graph:Graph[A],P:Array[Array[Option[int]]]) : List[Tree[Vertex[A]]] ={
        
   	val i_v = new HashMap[Int,Vertex[A]]()
    val v_i = new HashMap[Vertex[A],Int]()
    val n = graph.vertices.size
    
    graph.vertices.zipWithIndex.foreach(t => {
                                             i_v += t._2 -> t._1  
                                             v_i += t
                                            })
        
    var trees = List[Tree[Vertex[A]]]()

    graph.vertices.foreach(v =>{
		val i = v_i(v)
        val tree = Tree[Vertex[A]](v)
        for(j <- 0 to (n-1) 
            if j != i)
        {
        	val pathList:List[int] = path(i,j,P)//get the path list as a series of numbers 2::3::5::Nil etc.
            val p = pathList.map(i_v(_)) // get the vertices corresponding to those indices 
            merge(tree.root,p) // merge this new series with the existing shortest-path tree for the given vertex i
        }
        trees = trees ::: List(tree)
	})
    trees
  }
      
      
	private def path(i:int,j:int,P:Array[Array[Option[int]]]) : List[int] ={
	
	   if(P(i)(j).get == i){
	     j::Nil
	   }else{
	      path(i,P(i)(j).get,P):::path(P(i)(j).get,j,P)
	    }
	}
	  
	private def merge(root:Node[Vertex[A]],p:List[Vertex[A]]) : Unit = {
	  if(p.isEmpty) return
	    
	  root.getChild(p.head) match{
       case null => {
	     val node = Node(p.head)
	     root.addChild(node)
	     merge(node,p.tail)
	   }
	   case c:Node[Vertex[A]] => merge(c,p.tail) 
	   }
   }

}
